package com.example.lettcode._202410._20241022;

import com.example.lettcode.node.ListNode;

import javax.swing.*;
import java.util.ArrayList;
import java.util.List;

/*
92. 反转链表 II
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]
 */
public class _2_Fan_zhuan_lian_biao {

    public static void main(String[] args) {
        ListNode list1 = new ListNode(1);
        ListNode list2 = new ListNode(2);
        ListNode list3 = new ListNode(3);
        ListNode list4 = new ListNode(4);
        ListNode list5 = new ListNode(5);
        list1.next = list2;
        list2.next = list3;
        list3.next = list4;
        list4.next = list5;
        ListNode listNode = reverseBetween2(list1, 2, 4);
        System.out.println(listNode);
    }

    public static ListNode reverseBetween2(ListNode head, int left, int right) {
        if (head == null) {
            return head;
        }

        // 定义一个出参node
        ListNode ret = new ListNode(-1);
        ret.next = head;

        // 1、获取left前一个节点
        ListNode prevLeftNode = ret;
        for (int i = 0; i < left - 1; i++) {
            prevLeftNode = prevLeftNode.next;
        }

        // 2、获取right节点
        ListNode rightNode = prevLeftNode;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }

        // 3、获取left节点
        ListNode leftNode = prevLeftNode.next;

        // 4、获取right后一个节点
        ListNode nextRightNode = rightNode.next;

        // 5、独立出left->right的链表
        prevLeftNode.next = null;
        rightNode.next = null;

        // 6、将left->right链表反转
        ListNode tempLeftNode = leftNode;
        reverseLinkedList(tempLeftNode);

        // 6、重组链表
        prevLeftNode.next = rightNode;
        leftNode.next = nextRightNode;

        return ret.next;
    }

        public static ListNode reverseBetween(ListNode head, int left, int right) {
        // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        ListNode pre = dummyNode;
        // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
        // 建议写在 for 循环里，语义清晰
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }

        // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
        ListNode rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }

        // 第 3 步：切断出一个子链表（截取链表）
        ListNode leftNode = pre.next;
        ListNode curr = rightNode.next;

        // 注意：切断链接
        pre.next = null;
        rightNode.next = null;

        // 第 4 步：同第 206 题，反转链表的子区间
        reverseLinkedList(leftNode);

        // 第 5 步：接回到原来的链表中
        pre.next = rightNode;
        leftNode.next = curr;
        return dummyNode.next;
    }

    public static void reverseLinkedList(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
    }
}
